%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input and output
\Require A binary tree $T$ representing the Huffman code of an alphabet
  $A$. The root $r$ of $T$.
\Ensure A list $H$ representing a Huffman code of $A$, where $H[a_i]$
  corresponds to a Huffman encoding of $a_i \in A$.
%%
%% algorithm body
\State $H \gets [\,]$\Comment{list of Huffman encodings}
\State $Q \gets [r]$\Comment{queue of vertices}
\While{$\length(Q) > 0$}
  \State $\MyTreeRoot \gets \dequeue(Q)$
  \If{\rm \MyTreeRoot is a leaf}
    \State $H[\MyTreeRoot] \gets$ label of \MyTreeRoot
  \Else
    \State $a \gets$ left child of \MyTreeRoot
    \State $b \gets$ right child of \MyTreeRoot
    \State $\enqueue(Q, a)$
    \State $\enqueue(Q, b)$
    \State label of $a \gets$ label of \MyTreeRoot $+$ \MyZero
    \State label of $b \gets$ label of \MyTreeRoot $+$ \MyOne
  \EndIf
\EndWhile
\State \Return $H$
\end{algorithmic}
